package simple;

import sword.offer.common.GenerateList;
import sword.offer.common.ListNode;

/**
 * 将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
 * @author 胡宇轩
 * @Email: yuxuan.hu01@bianlifeng.com
 */
public class MergeTwoSortedLists {
    public static void main(String[] args) {
        Solution solution = new Solution();
        solution.mergeTwoLists(GenerateList.generate(new int[]{1,2,4}), GenerateList.generate(new int[]{1,3,4}));
    }
    /**
     * 将list2 合并到list1
     * 可以将list2中的元素一个个插入到list1, 从头到尾遍历list2中的元素，用list2的元素去list1中比较，找出该元素在list1
     * 中的位置。
     *
     * */
    static class Solution {
        public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
            if(list1 == null){
                return list2;
            }
            if(list2 == null){
                return list1;
            }
            ListNode pre = null;
            ListNode cur = list1;

            while(list2 != null && cur != null){
                // 找到位置了
                if(list2.val <= cur.val){
                    ListNode l2Next = list2.next;
                    list2.next = cur;
                    if(pre == null){
                        pre = list2;
                        list1 = pre;
                    }else{
                        pre.next = list2;
                        pre = pre.next;
                    }
                    list2 = l2Next;
                }else{
                    pre = cur;
                    cur = cur.next;
                }
            }
            if(list2 != null){
                pre.next = list2;
            }
            return list1;
        }
    }
}
